package alo.p6.work3;

import alo.p6.ThreadedBinaryTreeNode;

/**
 * @ClassName PreorderSuccessor
 * @Description 中序二叉树中查找前序后继
 * @Author Fanxc
 * @DATE 2021/2/6 11:25
 * @Version 1.0
 */
public class PreorderSuccessor {

    ThreadedBinaryTreeNode preorderSuccessor(ThreadedBinaryTreeNode P){
        ThreadedBinaryTreeNode Position;
        if (P.getLtag()==0){//如果P有左子树，返回P的左孩子结点
            return P.getLeft();
        }else {//如果P没有左子树，返回右子树包含P的最近结点的右孩子结点
            //直到P有右孩子
            Position=P;
            while (Position.getRtag()==1){
                Position=Position.getRight();
            }
            return Position.getRight();
        }
    }
}
